//给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为：
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]
// 
// Related Topics 数组 双指针

package com.yun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 【15】 三数之和
public class ThreeSum {
    public static void main(String[] args) {
        Solution solution = new ThreeSum().new Solution();
        int[] ary = {-1, 0, 1};
        System.out.println(solution.threeSum(ary));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums.length - i - 1; j++) {
                    if (nums[j] > nums[j + 1]) {
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
            }

            // int sum = -1; // 这里定义为负数，因为sum代表第二三个数的和，必须是正数，不会碰巧
            for (int i = 0; i < nums.length; i++) {
//                if (sum == -nums[i]) {
//                    continue;
//                }
//                if (nums[i] > 0) {
//                    break;
//                }
//                sum = -nums[i];
//                int tempJ = Integer.MIN_VALUE;
                if (i == 0 || nums[i] > nums[i - 1]) { // 跳过第一位，后面的都与之前比较，跟之前相等不进入循环
                    int j = i + 1, k = nums.length - 1;
                    while (j < k) {
//                    if (tempJ == nums[j]) {
//                        j++;
//                        continue;
//                    }
                        if (nums[j] + nums[k] > -nums[i]) {
                            k--;
                        } else if (nums[j] + nums[k] < -nums[i]) {
                            j++;
                        } else {
                            List<Integer> item = new ArrayList<>();
                            item.add(nums[i]);
                            item.add(nums[j]);
                            item.add(nums[k]);
                            result.add(item);
                            // important!!! 需要在成功命中之后，再设置tempJ临时数
                            // 如果在初始时就赋值，会出现移动一个指针，另一侧用于判断临时变量的相同，然后也移动了
//                          tempJ = nums[j];
                            j++;
                            k--;
                            while (j < k && nums[j] == nums[j - 1]) {
                                j++;
                            }
                            while (j < k && nums[k] == nums[k + 1]) {
                                k--;
                            }
                        }


                    }
                }
            }

            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
// 2019-11-1 10:49:27 可以优化，不用sum什么变量之类的，主要使用一个定值，左右指针碰撞达到效果
}